/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-04
 * Time: 8:50
 */
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        int[] dp = new int[array.length];
        dp[0] = array[0];
        // dp[i]: 以 array[i] 结尾的连续子序列的最大和
        // dp[i] 如果定义为其他的意义的话是不能达到最后的结果的
        // 所以 dp[i] 所包括的连续子序列中必须包含 array[i], 即 array[i] 是必须选的, 而它前面的可以不选
        for (int i = 1; i < array.length; i++) {
            // array[i] 是必须选的, 转移方程是要看前面的那一部分要不要
            dp[i] = dp[i-1] > 0 ? (dp[i-1] + array[i]) : array[i];
            max = Math.max(dp[i], max);
        }
        return max;
    }
}
